I. Field of the Invention
The present invention pertains generally to the field of communications and more particularly to constructing keyed permutations over a set of integers modulo-N for use in a message authentication code.
II. Background
A message authentication code (MAC) is a cryptographically derived item that may be appended to a particular message in order to verify that the message originated from a particular party and was not altered by any other party. It stands to reason that MACs find use in many fields of telecommunications. An exemplary field is wireless communications.
The field of wireless communications has many applications including, e.g., cordless telephones, paging, wireless local loops, wireless data applications such as personal digital assistants (PDAs), wireless telephony such as cellular and PCS telephone systems, mobile Internet Protocol (IP) telephony, and satellite communication systems. A particularly important application is wireless telephony for mobile subscribers.
Various over-the-air interfaces have been developed for wireless communication systems including, e.g., frequency division multiple access (FDMA), time division multiple access (TDMA), and code division multiple access (CDMA). In connection therewith, various domestic and international standards have been established including, e.g., Advanced Mobile Phone Service (AMPS), Global System for Mobile Communications (GSM), and Interim Standard 95 (IS-95).
An exemplary wireless telephony communication system is a code division multiple access (CDMA) system. The IS-95 standard and its derivatives, IS-95A, ANSI J-STD-008, IS-95B, proposed third generation standards IS-95C and IS-2000, proposed high-data-rate CDMA standards exclusively for data, etc. (referred to collectively herein as IS-95), are promulgated by the Telecommunication Industry Association (TIA) and other well known standards bodies to specify the use of a CDMA over-the-air interface for cellular or PCS telephony communication systems. Exemplary wireless communication systems configured substantially in accordance with the use of the IS-95 standard are described in U.S. Pat. Nos. 5,103,459 and 4,901,307, which are assigned to the assignee of the present invention and fully incorporated herein by reference.
One method for encrypting data sent over wireless systems is the Data Encryption Standard (DES), promulgated by the National Institute of Standards and Technology in FIPS PUB 46-2 (Dec. 30, 1993), which uses Feistel Networks to convert binary coded information into a cipher. A Feistel Network is used in the DES to convert a data block of length 64 bits. First, an initial permutation step is performed on the 64 bit block of data. The permuted data block is divided into two halves of length 32 bits, where one block is labeled L and the other is labeled R. An iterative procedure then manipulates the blocks using the following relationships:Li=Ri−1,Ri=Li−1⊕ƒ(Ri−1,Ki),where Ki is the subkey used in the ith round and ƒ is an arbitrary function. The function ƒ is also referred to as a “round” function because each iterative step is referred to as a round. In the DES algorithm, round function ƒ is composed of four operations. First, a 48 bit subkey is selected from the 56 bits of a key. Then the round function ƒ comprises the steps of expanding the right half block of the data from 32 bits to 48 bits via an expansion permutation, combining this result with the 48 bit subkey via an XOR operation, sending the result through 8 substitution boxes, which produces 32 additional bits, and permuting the results. The output of function ƒ is combined with the left half block through another XOR operation and the result is used as the new right half block, while the old right half block is used as the new left half block for the next round. The DES round is reversible because ƒ can be reconstructed in each round to satisfy the relationship, Li−1⊕ƒ(Ri−1, Ki)⊕ƒ(Ri−1, Ki)=Li−1.
Due to the binary format of data blocks, prior art methods such as DES encrypt a plaintext message, whose elements are members of the set of Cartesian products Z2×Z2× . . . ×Z2 for n terms, into a ciphertext message, whose elements are also members of the set Z2×Z2× . . . ×Z2 for n terms. As used herein, Zm is a cyclic group {0, 1, . . . , m−1} under addition modulo m. Hence, the purpose of DES is not to change the order of the bits in a plaintext (e.g., original data) message. Rather, the purpose of DES is to generate a ciphertext wherein each of the bits of the ciphertext depends on all of the bits of the plaintext.
Since DES is reversible and converts 264 inputs to 264 outputs under the control of a key, DES can also be viewed as a method for a key to choose a permutation of the set of integers {0, 1, . . . , 264−1}, such that the permutation chosen by the key must remain concealed from unauthorized parties.
In a typical communication, the MAC is the output of a function, wherein a message and a shared secret key K, known only by the message originator and recipient, are the inputs to the function. If the particular function chosen is secure, then an active attacker who can intercept and potentially modify the messages sent can neither discover the key K nor create messages that will be accepted by the recipient as valid with a reasonable probability.
A new type of MAC has been proposed in U.S. patent application Ser. No. 09/371,147, entitled, “METHOD AND APPARATUS FOR GENERATING A MESSAGE AUTHENTICATION CODE,” filed on Aug. 9, 1999, which is assigned to the assignee of the present invention and fully incorporated herein by reference, wherein the MAC relies on reordering the bits of an m-bit data block under the influence of some key, and constructing an x-bit cyclic redundancy check (CRC) that is a linear function of the reordered m-bit block. This MAC is referred to as a CRC-MAC. A sender transmits the original m-bit data block along with the CRC-MAC to a receiver. The receiver uses the shared key to re-order the bits of the received data message. The receiver will then compute a CRC from the resulting block. Using this method, a receiver is able to detect if the data was altered in transit and to correct a small number of errors that may have occurred during transmission, while still making it difficult for an active attacker to forge or alter messages.
It is well known that m and x are optimal when m+x=2x−1−1. The construction of an x-bit CRC-MAC is discussed in more detail in U.S. patent application Ser. No. 09/371,147. Those of ordinary skill in the art know that a 16-bit CRC proves to be of particular use in the field of wireless communications. Using the number x=16 in the relationship above, the optimal size of a data block for construction of a CRC-MAC is m=(215−1)−16=32,751 bits.
As described above for the optimal values of m and x, the CRC-MAC requires a method for using a key to construct an m-bit intermediate block, wherein m=(2x−1−1), by re-ordering the bits of the original m-bit data block. As described in U.S. patent application Ser. No. 09/371,147, the construction of an m-bit intermediate block can be performed using two algorithms. The first algorithm processes each of the indices to the bits in the m-bit data block. For each index x associated with each bit position of the m-bit data block, the first algorithm calls on the second algorithm to determine a unique index y in the same range as x, wherein y is determined from x and a shared secret key. The first algorithm then sets the value in bit position y of the intermediate block to the value of the bit in position x of the data block.
After the first algorithm has performed these steps for each of the indices x in the range {0, 1, . . . , m−1}, the intermediate block will be an m-bit block that contains the bits of the data block in a different order. For the CRC-MAC to be secure, it is necessary that, for any given key, the first algorithm does not place two bits from the data block in the same position of the intermediate block. This condition is satisfied only if, for each key, the second algorithm defines a one-to-one mapping for the set {0, 1, . . . , m−1} onto itself. A one-to-one mapping is commonly referred to as a permutation in the art. Therefore, the CRC-MAC requires a method that uses a key to define a permutation on the set {0, 1, . . . , m−1}. Furthermore, the permutation chosen by the key must remain concealed from unauthorized parties.
DES can be considered as a method for using a key to determine a permutation over the set of integers {0, 1, . . . , 264−1}, such that the permutation chosen by the key must remain concealed from unauthorized parties. If the value of m were 264, then the DES would satisfy the requirements for the second algorithm. However DES and other block ciphers cannot be used as the second algorithm because such ciphers have only been constructed for the purpose of creating one-to-one relationships between sets of order 2M, and do not define one-to-one relationships between sets of other orders. Otherwise, the properties of a block cipher satisfy the conditions required for the second algorithm, and the second algorithm would be implemented for the same notion of security.
Some public-key encryption algorithms, such as the RSA algorithm and the El-Gamal algorithm, disclose methods for a key to define a permutation on ZN for certain values of N other than power of two. However, these methods should not be used with CRC-MACs because these public key algorithms are insecure for small values of N, such as 32,751. For the values of N that are required for the CRC-MAC, the permutation chosen by a key must be concealed from unauthorized parties.
Hence, there exists a present need to permute a large number N of data bits for the CRC-MAC. In the optimal case referred to above, the data block should contain 32,751 bits. As described above, permuting N bits requires a method for a key to define a permutation on the set {0, 1, . . . , N−1}=ZN such that the permutation chosen by the key remains concealed from unauthorized parties. Such a method is required that is applicable for any value of N, where N can be either composite or prime. A prime number is an integer greater than 1 whose only factors are 1 and itself. A composite number is an integer greater than 1 that is not prime. Such a method can be applied in a wide variety of applications beyond message authentication and error-correction in telecommunications systems.